(1) Field of the Invention
The present invention relates to cryptography as an information security technique, and more particularly, to elliptic curve cryptosystems.
(2) Description of the Related Art
In recent years, communication and pay-per-view television delivery via a public digital network have become popular. However, using a public network does not ensure security: the trouble of wiretapping and fraud by a third party and wrong data-transmission can not be eliminated completely. Given these circumstances, a digital signature or verification and a privacy communication have gained considerable importance. The privacy communication referred herein means a communication with an intended party without any information leakage, and the digital signature or verification referred herein means an authentication of the validity and a message sender to a receiver. The digital signatures or verification and private communication include a communication method called a public-key cryptosystem (PKC). The PKC facilitates the management of enciphering keys held in secret by each party, and thus it is an indispensable, basic technique in a cryptosystem where a plurality of parties are involved. In the following, the PKC's principle and procedure will be explained with its historical background.
(1) Privacy Communication Using DLP (Discrete Logarithm Problem) over Finite Field
(Principle)
Let p be a prime number, g be one of p's primitive roots, u be an arbitrary natural number, and .alpha. be a residue of g to the u'th power modulo p, g.sup.u .ident..alpha. (mod p). Then, it is easy to find .alpha. with given g, p and u. However, it is quite difficult to find u using g, p and .alpha. even with a state-of-the-art massive computer if p is a prime number of about 140 digits. The same can be said in the following: it is easy to find the product of two prime numbers r and s, but it is quite difficult to find r and s from the product by factorization if r and s are prime numbers of about 140 digits; for the product is a number of about 280 digits.
Next, let v be another arbitrary natural number, .beta. be a residue of g to the v'th power modulo p, g.sup.v .ident..beta. (mod p). Here, a residue of .alpha. to the v'th power modulo p equals to a residue of .beta. to the u'th power modulo p. EQU .alpha..sup.v .ident. (g.sup.u).sup.v .ident.(g.sup.v).sup.u .ident..beta..sup.u (mod p).
(Procedure)
In the following, a common key cryptosystem will be explained with referring to FIG. 1 as an example of the procedure of the privacy communication using the DLP over a finite field using the above principle.
A network provider notifies p and g to each user.
User U selects an arbitrary natural number u to compute .alpha. by an arithmetic operation of g.sup.u .ident..alpha. (mod p).
Likewise, User V selects v to compute .beta. by an arithmetic operation of g.sup.v .ident..beta. (mod p).
User U notifies .alpha. to User V via a public network while keeping u in secret, and User V notifies .beta. to user U via the public network while keeping v in secret.
Both users compute a residue k.sub.uv of g.sup.uv modulo p, which will be secretly used as a common key between themselves.
Here, k.sub.uv .ident.g.sup.uv (mod p).
The above procedure will be explained more specifically by using a small prime number as an example for the use of convenience.
Now, let p=11, g=2, and let User U select 4 as u, then g.sup.u =2.sup.4 =16 and since a reside of 16 modulo 11 is 5, .alpha.=5. Likewise, let User V select 8 as v, then g.sup.v =2.sup.8 =256 and since a residue of 256 modulo 11 is 3, .beta.=3. Further, since a residue of both .alpha..sup.v =5.sup.8 and .beta..sup.u =3.sup.4 modulo 11 is 4 (mod 11), k.sub.uv =4.
When sending a message, or bit information, to User V, User U enciphers the message by dividing the same into a plurality of sets of a certain number of bits, and by performing an arithmetic operation with k.sub.uv for each set.
Let the message be (010). k.sub.uv =4, this is expressed as (100) in the binary system. For this reason, if the arithmetic operation is an exclusive OR, then the message is enciphered as {(010) XOR (100)=} (110).
Then, User U sends the enciphered message to User V.
Upon the receipt of the enciphered message, User V deciphers the same using k.sub.uv to obtain the original message.
If User V receives (110) as the enciphered message, the enciphered message is deciphered as {(110) XOR (100)=} (010).
Note that the arithmetic operation can be addition, subtraction, and logic calculus per bit in the binary system.
The security of the foregoing common key cryptosystem depends on that should a third party wiretap .alpha. and .beta. when Users U and V exchange the same, he can not find k.sub.uv unless he knows u or v.
Also, since k.sub.uv is known to only Users U and V, User V can identify User U as the message sender if he can authenticate the deciphered message.
The foregoing common key cryptosystem is advantageous in that it can be applied to a communication where a plurality of users are involved. Other users W, X, etc. can join the privacy communication by selecting their natural numbers w, x, . . . , respectively. For example, User W can communicate with User U by using a reside of g.sup.u.multidot.w modulo p as the common key.
Further, each of Users U, V, W can regularly replace their respective natural numbers u, v, w, . . . , etc. with other natural numbers u', v', w', . . . , etc. respectively, or specific User U can select other natural numbers u.sub.1, u.sub.2, . . . , etc. for each communication party. For this reason, if the forgoing common key cryptosystem is employed in a corporation's internal network system, it can be easily updated to an organization restructuring.
Note that, in practice, a product of a plurality of sufficiently large prime numbers p, q, r, . . . or p to the second or third power may be used instead of the prime number p, and the primitive root g may be replaced with a natural number whose order is sufficiently large.
However, parallel with the advancement in the field of computer technology, the mathematical logic has developed a variety of methods to find u using g, p, and .alpha. with a relatively small amount of computation.
One of the counter methods that uses the prime number p of about 200 digits instead of the prime number p of about 30 digits has been proposed. However, this method is not favorable because the absolute amount for various required computations may increase in proportional to the digit numbers.
Given these circumstances, the privacy communication using the EDLP (Discrete Logarithm Problem on an Elliptic Curve) has been proposed, which will be explained in the following.
(2) Privacy Communication Using EDLP
The EDLP, which is discussed in "A Course in Number Theory and Cryptography", Neal Koblitz, Springer-Verlag, 1987, will be explained.
(Elliptic Curve and Arithmetic Operation on Elliptic Curve)
An elliptic curve is an abelian manifold, or a projective algebraic curve with an irreducible and a non-singular genus 1 given by, for example, EQU Y.sup.2 =X.sup.3 +aX+b.
Now, let BP.sub.1 and BP.sub.2 be points on the elliptic curve, then an arithmetic operation BP.sub.1 +BP.sub.2 can be defined as follows:
Let BP.sub.3 ' be a symmetric point to BP.sub.3 with respect to an x-axis, and BP.sub.3 be an intersection of the elliptic curve and a straight line passing both BP.sub.1 and BP.sub.2, then BP.sub.3 ' is BP.sub.1 +BP.sub.2, which is shown in FIG. 2. If BP.sub.1 =BP.sub.2, then the straight line passing BP.sub.1 and BP.sub.2 is a tangential line at BP.sub.1.
Let E be the elliptic curve, then it is E{GF(q)} that is used for the encryption; here, q is a power of a prime number, GF(q) is a finite field (Galois Field), and E{GF(q)} is a group of elements over GF(q) on the elliptic curve E.
For example, let the elliptic curve E be given by y.sup.2 =x.sup.3 +3x+2, and q=5, then E{GF(q)} is a set of five elements: (1, 1), (1, -1), (2, 1), (2, -1) and a point at infinity.
(Principle)
Next, the properties of E{GF(q)}, or the principle of the basis of the privacy communication, will be explained.
Let an element BP of E{GF(q)} be a basepoint such that whose order is divisible by a large prime number, and d be an arbitrary natural number. Then it is easy to find d.multidot.BP using BP and d (add BP d times), but it is by no means easy even with a state-of-the-art computer to solve a following problem if BP or q etc. is a natural number of about 30 digits: given an elements BP and Q of E{GF(q)}, find a natural number d such that Q=d.multidot.BP, if such a natural number d exists. Here, BP plays a role of g over the finite field GF(q) modulo p.
(Procedure)
The procedure is substantially the same as the above case over the finite field.
In other words, the aforementioned p corresponds to E{GF(q)}, g to BP, u or v to d, and an arithmetic operation, such as finding a residue of g to the u'th power modulo p, is performed over E{GF(q)} instead of GF(p).
Note that each point on the elliptic curve is given two-dimensional coordinates (x, y) whereas the message is one dimension. For this reason, one of the x- and y-coordinates is used in accordance with a prior agreement between the users. Thus, the procedure is different in that data are additionally transmitted for each transmission to make it possible to determine which coordinate was used, etc. (3) Current Development on Privacy Communication Using EDLP
In 1991, a method to solve the EDLP relatively easily by reducing the same to the DLP was proposed, although any other sub-exponential method has not been proposed yet. With the sub-exponential method, a typical EDLP over a definition field of about 100 bits can be easily solved. This method proposed in 1991 is called MOV reduction and discussed in "Reducing Elliptic Curve Logarithm to Logarithms in a Finite Field", A. Menezes, S. Vanstone, T. Okamoto, STOC 91. In the MOV reduction, let q be a power of a prime number, E be an elliptic curve defined over the finite field GF(q), and E{GF(q)} be a group of elements over GF(q) on E. Then, the EDLP having BP.epsilon.E{GF(q)} as its base is reduced to the DLP over an extensive GF(q.sup.r) of the finite field GF(q) when the order of BP and q are relatively prime; in particular, the discrete logarithm problem on a super singular elliptic curve can be solved by being reduced to the DLP over an extensive at most GF(q.sup.6) of the finite field GF(q).
Accordingly, methods to construct an irreducible elliptic curve to the MOV reduction have been proposed. A variety of these methods have been proposed, and they are discussed in, for example, "Non-Supersingualr Elliptic Curves for Public Key Cryptosystems", T. Beth, F. Schaefer, Eurocrypt 91, 1991, or "On ordinary elliptic curve cryptosystems", Atsuko Miyaji, Abstract of Asiacrypt '91., etc. Since there has been proposed no solution such that gives a sub-exponential algorithm, the EDLP, which is as secure as the DLP over a finite field, can be constructed over a considerably small definition field by these methods.
However, only using a smaller definition field does not increase the operation speed much, because one elliptic curve addition requires twelve or thirteen multiplications. In other words, let BP.sub.1 and BP.sub.2 be expressed as (x.sub.1, y.sub.1) and (x.sub.2, y.sub.2), then BP.sub.1 +BP.sub.2 ={f.sub.1 (x.sub.1, y.sub.1, x.sub.2, Y.sub.2), f.sub.2 (x.sub.1, Y.sub.1, x.sub.2, Y.sub.2)}, where f.sub.1 and f.sub.2 are functions for twelve or thirteen computations over GF(p). Thus, a method to speed up the operation has been developed together with the method to avoid the MOV reduction, which will be explained in the following.
(4) Method to Increase Operation Speed of Elliptic Curve Cryptosystem
One of the methods to increase the operation speed in the elliptic curve cryptosystem is discussed in "CM-curves with good cryptographic properties", N. Koblits, Crypro'91, 1991.
FIG. 3 shows a brief procedure for constructing an elliptic curve that speeds up the conventional methods of generating digital signatures or verification and privacy communication.
In the following, the conventional procedure will be explained with referring to FIG. 3.
(S1) Determination of Prospective Elliptic Curve
Choose two anomalous elliptic curves having GF(2) as the definition field. EQU E.sub.1 :y.sup.2 +xy=x.sup.3 +x.sup.2 +1 EQU E.sub.2 :y.sup.2 +xy=x.sup.3 +1
The group E{GF(2.sup.m)} consisting of the elements over GF(2.sup.m) on the elliptic curve E is as follows: ##EQU1## where .infin. is an infinite point. (S2) Determination of Suitable Extension Degree m.
As has been stated, it is known that the EDLP, on which the security of the PKC is based, is easily solved unless the order of the element BP, or the basepoint, has a large prime factor.
A necessary and sufficient condition for the element BP to have a large prime factor as its order is that the number of the elements of E{GF(q)} has a large prime factor.
Thus, for the elliptic curve E.sub.i described in (S1), m such that the number of elements, #E.sub.i {GF(2.sup.m)}, is divisible by a large prime factor is found. Here i=1, 2.
Note that given a specific m, etc, the number of elements on various types of elliptic curves such as E{GF(2.sup.m)} can be computed more precisely due to the researches by Hasse and Due. For example, the above mentioned #E.sub.i {GF(2.sup.m)} has an order of about 2.sup.m.
(S3) Construction of Elliptic Curve
To have the prime factor of 30 or more digits means that m is about [30 log.sub.2 10], where [ ] denotes Gauss'notation. With some of such m's found by trial-and-error, whether or not #E.sub.i {GF(2.sup.m)} has a prime factor of 30 or more digits is examined based on a formula that gives #E.sub.i {GF(2.sup.m)}. Finding the number of elements of the group E.sub.i {GF(2.sup.m)} consisting of the elements on the elliptic curve E.sub.i {GF(2.sup.m)} and factorizing the same yields: EQU if m=101, then #E.sub.1 {GF(2.sup.m)}=2.times.p.sub.1 EQU if m=131, then #E.sub.2 {GF(2.sup.m)}=4.times.p.sub.2
where p.sub.1 and P.sub.2 are prime numbers. Also, it can be confirmed that the finite filed embedded by the MOV reduction is sufficiently large.
Thus, it can be concluded that the PKC can be constructed if it is based on the EDLP having E.sub.2 {GF(2.sup.131)} with the basepoint BP whose order has exactly P.sub.2, or the EDLP having E.sub.i {GF(2.sup.101)} with the basepoint BP whose order has exactly p.sub.1.
Now, with the anomalous, if T is a map to E(x.sup.2, y.sup.2) from E(x, y); then [2] (two times)=T-T.sup.2, which is discussed in "The arithmetic of elliptic curves", J. H. Silverman, Springer-Verlag, 1986. In other words, if BP=(x, y), then 2BP=(T-T.sup.2) (x, y)=(x, y)-(x.sup.2, y.sup.2). Thus, with the elliptic curve constructed in this way, 2.sup.k BP={BP=(x, y); k=1, 2, 3, 4} can be computed as follows: ##EQU2## where the superscript 2 3 and the like denote 2.sup.3 etc.
In case of the arithmetic operation over an extension of GF(2), the computation by a second power is realized by a cyclic shift when a normalized base is used as a base, so that the operation speed can be neglected when it is realized by a hardware. Accordingly, 2.sup.k BP (k=1, 2, 3, 4) is realized by two elliptic curve additions, and the operation speed increases. In case of E.sub.2 particularly, the normalized base over the definition field GF(2.sup.131) is an optimal normalized base, and the number of times for ANDs and exclusive ORs necessary for one multiplication is minimized. As a result, the basic arithmetic operation (multiplications over a finite field) can be performed faster. The optimal normalized base referred herein is a number whose number of terms of multiplicative function has 2.sup.m -1. For further information, see "Optimal Normal bases in GF(p.sup.a)", R. C. Mullin et al, Discrete Applied Mathematics 22, pp. 149-161.
(5) Problems with Conventional Elliptic Curve to Increase Operation Speed
However, the above method does not speed up one elliptic curve addition. Therefore, to further increase the speed, it is necessary to find an elliptic curve satisfying the condition to speed up the arithmetic operation (the finite field GF(2.sup.m) having an optimal normalized base} and the condition for an elliptic curve that is secure and simplifies 2.sup.i -fold point (i=1, 2, 3, 4) (anomalous elliptic curve whose number of elements is divisible by a large prime number). However, there are only a handful of such elliptic curves; for these two conditions are not implicated each other.
(6) Other Method to Speed-up Elliptic Curve
(Addition Chain)
The addition chain is proposed as one of the methods to increase the computation speed of kBP on the elliptic curve. In the addition chain, for example, 7BP is not found by simply adding BP seven times, but it is found by 2(2(2BP)-BP, one subtraction which is the same computation amount as an addition and three doublings; this is an invention of an addition method and will be studied along with the addition chain in the computation over a finite field g.sup.k. This study relates to an invention of a pre-computation table and computation sequence, which are discussed in "Some algorithms on addition chains and their complexity", M. J. Coster, Center for Mathematics and Computer Science Report CS-R9024. Compared with the above-method that simplifies 2.sup.i -fold point (i=1, 2, 3, 4), the addition chain is faster for the computation of k.multidot.BP.
(Finite Field)
In addition, various methods to speed up the cryptosystem using the finite field have been proposed as well. However, since a finite field is used, these methods are impossible without using a large definition field in the privacy communication to ensure the security, which is discussed in "Discrete logarithm in GF(p) using the number field sieve" D. M. Gordon, to appear in SIAM Journal on Discrete Math.
(7) Current Problem with Elliptic Curve
There is a need for a high-speed operation for the PKC whose security depends on the EDLP. In case of the first conventional method, where only c.multidot.BP for a specific natural number c is sped up, it is difficult to increase the speed by combining the addition chain when k.multidot.BP for a general natural number k is to be sped up. Also, if an elliptic curve such that satisfies the condition to speed up c.multidot.BP for the specific c and the condition to speed up the basic arithmetic operation is constructed, a definition field becomes larger. Thus, it is a problem for the digital signature or verification and private communication to construct an elliptic curve such that uses a small definition field and speeds up the arithmetic operation of k.multidot.BP for the general natural number, and such that is easily combined with the addition chain and speeds up the basic arithmetic operation.
To further ensure the security, a possibility that security degradation in one system jeopardizes the entire system such as transactions based on the privacy communication, or a possibility that the security of one system happens to be degraded must be maintained small. For this reason, it is desirable to replace cryptosystem parameters regularly for each communication party, transmission purpose, etc., or within one cryptosystem. Note that this must be done in such a manner that minimizes the amount of change and maintains the same performance efficiency (speed and memory size, etc.). This corresponds to the regular replacement of p over a finite field, which has been described in the above.
However, in the above conventional methods, since an elliptic curve over GF(2) is extended to GF(2.sup.m), it is difficult to construct an elliptic curve that does not change the system performance. Thus, it is a problem for the digital signature or verification and private communication to construct an elliptic curve such that facilities the cryptosystem parameter replacement either for each system or within one system at any time when the replacement is required while minimizing an amount of change such as memory size, and enables high-speed arithmetic operation.
Further, in the above cases, it is a problem that there is a condition that the MOV reduction can not be applied to the elliptic curve.